Many approaches have been developed for encoding machine readable information on objects. Perhaps the most well-known technique is the ubiquitous barcode. Over the years, various barcode types have been created, which differ significantly from the name-sake pattern of dark linear bars on a lighter background. Now, the term barcode has been used to encompass machine symbols in various shapes, sizes, patterns and colors.
These types of codes were primarily developed to be reliable data carriers that could be applied with a wide array of print and marking techniques on many types of objects. They were not designed, in most cases, to be aesthetically pleasing, or to be weaved into other imagery, whether it be graphical designs, text etc. on product packaging, labels, or displays. As such, in most applications, these codes occupy a dedicated location on an object, where no other information is located. This approach has worked well to reliably apply identifying information to objects, including packaging, parts (“Direct Part Marking”), etc. Nevertheless, placing the code at a dedicated location limits the ability to find and read the code. When used on consumer goods, it is often located on the back or bottom of the item so as not to interfere with consumer messaging and product aesthetics. This placement of the code tends to slow down code reading or increase scanner cost by requiring additional components to capture multiple views of an object. It also increases risk of injury due to the need for workers to re-position the object to scan the code for auto-identification. Obviously, this undermines the theoretical speed and reliability advantages of auto-identification.
Data signaling techniques have been developed that have promise in addressing these drawbacks while providing additional advantages. One such technique is referred to as digital watermarking. Digital watermarking provides a method of encoding information within image content or object surface topology. As such, it can be applied over the entire surface of the object within minimal cost and changes to workflow, addressing the drawbacks of barcodes while being fully compatible with them. Additionally, the digital watermarking applies to many different types of media, including analog and digital forms of images (including video) and audio. This enables enterprises to implement auto-identification and auxiliary data encoding across all of their assets, including physical and digital media.
Watermarking advantageously exploits the existing image or audio information as a carrier of additional information. This additional information is often referred to as the “watermark payload,” a variable sequence of message symbols inserted per unit of host content. There are, of course, limits to the extent to which this payload can be inserted in existing image or audio (the host signal) without impacting the perceptual quality of the host. Generally speaking, host signals with more variable information provide greater opportunity to insert the payload, whereas host signals with uniform or solid tones provide less opportunity for insertion of the payload. In cases where there is little host signal content, it may not be possible to encode the payload, or if it is encoded, it is done so with a greater impact on perceptual quality.
Perceptual quality relates to the extent to which a human perceives a change in an image. This is a challenging metric, as it has a significant subjective component. Nevertheless, the human visual system has been modeled, and data from user tests can be used to construct a classifier that measures in a quantitative way, whether a change to an image or video will be visible or deemed objectionable. Human visual system models and classifiers based on them provide a measure of whether a change made to an image is likely to be visible, and also, can quantify visibility in units such as Just Noticeable Difference (JND) units. For applications where images are modified to insert a data signal, the perceptual quality is a constraint on data signal design and encoding strategy. The importance of this constraint on signal design and encoding methodology varies with the application. The flexibility of the watermark signal allows it to be transformed into visual elements of the object's design in various ways, and as such, provides many options for adapting the signal to satisfy perceptual quality constraints for different types of images and applications.
Literature documenting our earlier work describes various ways to deal with host signal types that lack signal content compatible with data encoding. We refer to one approach as “sparse” marking as the data carrying signal is formed as a sparse array of signal elements. For visual media, the sparse array of elements works well on portions of a host image that are uniform or solid tones or appear largely blank. With greater sophistication in the signaling, it also is effective in encoding blank areas around text of a document, label, visual display or package, as our signaling schemes employ robust data encoding strategies to mitigate impact of interference from the text. In one embodiment, a sparse mark is comprised of a pattern of spatial locations where ink is deposited or not. For example, the sparse signal may be comprised of ink dots on a light background, such that the signal forms a pattern of subtly darker spatial locations. The signal is designed to be sparse by the spacing apart of the darker locations on the light background. Conversely, the signal may be designed as an array of lighter “holes” on a relatively darker background. See, for example, U.S. Pat. Nos. 6,345,104, 6,993,152 and 7,340,076, which are hereby incorporated by reference in their entirety.
As described in U.S. Pat. No. 6,345,104, this strategy of forming patterns of light and dark elements is consistent with our earlier digital watermarking strategies that modulate luminance. For example, a lighter element encodes a first message symbol (e.g., binary one), while a darker element encodes a second symbol (e.g., binary zero).
The sparse signal has minimal impact on visual quality due to its sparse arrangement. However, the trade-off for applications like automatic object identification is that more sophistication is required in the data signaling methodology to ensure that the data carried within the sparse signal may be reliably and efficiently recovered in many different and challenging environments. The sparse nature of the signal dictates that less payload may be encoded per unit of object surface area. Further, within the sparse signal, there is a trade-off between allocating signal for payload capacity versus signal for robustness. In the latter category of robustness, the signaling scheme must support recovery in environments of geometric distortion, which occurs when the sparse signal is imaged from various angles, perspectives and distances, in the presence of noise of various types that tends to interfere with the data signal.
There are various sources of geometric distortion that need to be addressed to reliably recover the payload in the sparse signal. Examples of geometric distortion include signal cropping and warping. Cropping truncates portions of the sparse signal, e.g., in cases where only a portion is captured due to occlusion by other objects or incomplete capture by a scanner. Warping occurs when the surface on which the sparse signal is applied is curved (on cups or cans) or wrinkled (on bags and flexible plastic or foil pouches) and when the sparse signal is imaged from a surface at various perspectives.
The design of a signaling scheme must also account for practical challenges posed by constraints on digital circuitry, processors and memory for encoding and decoding. These include computational efficiency, power consumption, memory consumption, memory bandwidth, use of network bandwidth, cost of hardware circuitry or programmable processors/circuitry, cost of designing and integrating encoders and decoders within signal transmitter and receiver, equipment, etc. For example, some encoding schemes may provide optimized encoding or decoding, but may not be applicable because they are too slow for encoding or decoding in real time, e.g., as the host signal is being transmitted, received, updated, or being processed with multiple other signal processing operations concurrently.
The design must also account for practical challenges of the marking technology. The printing technology must be able to reproduce the signal reliably. This includes transformation of the data signal in the Raster Image Processor as well as application of an image to an object.
The design must also account for practical challenges posed by image capture and associated optics. Scanners at Point of Sale (POS), for example, tend to be tuned to detect black and white bar codes (e.g., with a spectral range that focuses on image capture around image content at a wavelength at or around 660 nm), and as such, the illumination type and sensors may have a much more limited range of spectral bands and resolutions that the device can sense.
Sparse signaling is particularly challenging in that the sparse nature of the signal provides less opportunity to include signal for payload and robustness. In particular, there is less opportunity to include payload and synchronization. The strategy for synchronization may rely on an explicit synchronization (“sync”) component or an implicit synchronization component. In the latter case, the encoding of the payload may be arranged in a manner that provides a pattern that facilitates detection and synchronization.
Another important consideration for some applications is compatibility and inter-operability with other messaging protocols. For example, in the case of applying identification over the surface of objects, the signal encoding and decoding strategy should preferably support various protocols to deal with various image types, printing technologies, and scanner technologies. This design consideration dictates that sparse signaling should be compatible with encoding and decoding other signaling, like legacy encoding schemes on older objects and dense watermark signaling strategies and barcodes of various types. Preferably, the installed base of decoder technology should be able to efficiently decode signals from various signaling types, including new sparse signal arrangements.
One aspect of the disclosure is a method for inserting a sparse, variable data carrying signal into an image. This method provides a first signal component, which facilitates a synchronization function of the sparse signal. It also provides a second signal component that is modulated to carry a variable data signal. The first and second signal components have values located at coordinates within a two-dimensional block. The method combines the first signal component and the second signal component to produce the sparse, variable data carrying signal by setting sparse elements at coordinates within the two-dimensional block where the first and second component signal values provide compatible modulation of the image. The method inserts the sparse, variable data carrying signal into at least a first image layer or channel of an image design.
In this method, the sparse signal elements are set at coordinates where the signal components provide compatible modulation. Compatible modulation is where the signals of the two components comply with a consistency rule. For example, the signals have a consistent direction of modulation of an optical property at a coordinate within the two-dimensional block. One optical property is brightness or lightness and it may be modulated in a darker or lighter direction. Other examples of optical properties are chrominance and hue. Components that modulate an image in the same direction, e.g., both darker or both lighter, have a compatible modulation direction.
The consistency rule may also be determined by consistency in amount of modulation. For instance, modulation of the components is compatible if the value of signal components fall within a common range bounded by at least one threshold. In some cases, components are multi-valued, and then quantized to quantization levels or bins (multi-dimensional values falling in a bin space are quantized to a bin). This may be implemented by applying a threshold, in which values within a range are set to a particular value. Multi-valued components are converted into binary levels (e.g., 1 or 0) or more than two levels (e.g., 1, 0, −1), for example. The consistency rule is evaluated on the output of this process by comparing the values of the signal components at a coordinate and setting sparse element or not at the coordinate based on the consistency. A logical AND operation or like comparison may be used to determine whether the signal components satisfy the consistency rule, e.g., quantize to a common quantization level or range bounded by a threshold.
The quantizing of a signal can be used to determine a distribution of sparse elements in a block. In one embodiment, for example, a signal component (e.g., sync component) is quantized to provide a sparse distribution within a block. The sparse signal is then formed based on where the signal components comply with a consistency rule. The consistency rule evaluates signal components at these locations and sets a sparse element at the coordinate where they are consistent.
Another aspect of the disclosure is a method for inserting a sparse, variable data carrying signal into an image that employs orthogonal signal components. First and second orthogonal components are provided, with at least one of them modulated with variable data. The orthogonal components are combined to produce a sparse, variable data carrying signal by selecting a subset of the first and second orthogonal components. This sparse signal is then inserted into at least a first image layer of an image design. The components may be quantized into sparse signals, and then combined. Alternatively, they may be combined and then quantized into a sparse signal.
Another aspect of the disclosure is an alternative method for inserting a sparse, variable data carrying signal into an image. In this method, a sparse pattern of elements at coordinates within a two-dimensional block is provided, along with a signal component that is modulated to carry a variable data signal. The method generates a sparse, variable data carrying signal by distributing the signal component within the two-dimensional block based on the location of the sparse pattern of elements. In one such approach, the signal component is converted to a sparse, variable data carrying signal by removing signal elements of the signal component at coordinates where the signal component does not coincide with coordinates of the sparse pattern. The signal component is repeated in two-dimensional blocks within the image. Different sparse patterns may be used to distribute the signal component differently in the blocks.
In this document, we detail various sparse signaling schemes, including schemes for generating signals, and encoding and decoding them in various object types and object marking technologies. We describe schemes that encode a sparse signal within host signal carrier in a manner that is robust, flexible to achieve perceptual quality constraints, and provides improved data capacity.